package puzzle.projecteuler.p200;

import java.math.BigInteger;
import java.util.List;

import astudy.util.AdvMath;
import astudy.util.AdvMath.Factors;

public class Problem130C {

	public static void main(String[] args) {
		long s = System.currentTimeMillis();
		int count = 25;
		long sum = 0;
		long n = 2;
		while (count > 0) {
			if (n%2 == 0 || n%5 == 0 || AdvMath.isPrime(n)) {
			} else {
				long a = A(n);
				if ((n-1)%a == 0) {
					count --;
					sum += n;
					System.out.println(n);
				}
			}
			n ++;
		}
		System.out.println("sum = " + sum);
		System.out.println((System.currentTimeMillis() - s) + " ms");
	}

	public static long A(long n) {
		
		n = 9*n;
		long phi = AdvMath.phi(n);
		List<Factors> fs = new Factors(phi).getAllFactors();
		long f = 0;
		for (int i = 0; i < fs.size(); i ++) {
			f = fs.get(i).longValue();
			BigInteger tmp = BigInteger.TEN.modPow(BigInteger.valueOf(f), BigInteger.valueOf(n));
			if (tmp.compareTo(BigInteger.ONE) == 0) {
				break;
			}
		}
		return f;
	}
}
